package leetcode_301_400;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeeCode_368 {
    public static void main(String[] args) {
        System.out.println(largestDivisibleSubset(new int[]{1, 2, 3}));
        System.out.println(largestDivisibleSubset(new int[]{1, 2, 4, 8, 16}));
        System.out.println(largestDivisibleSubset(new int[]{3,4,8,16}));
    }
    static class Node{
        int val;
        List<Integer> list;
    }
    private static List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        int max = 0;
        int index = 0;
        Node[] dp = new Node[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new Node();
            dp[i].list = new ArrayList<>();
            dp[i].list.add(nums[i]);
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0){
                    if (dp[j].val + 1 > dp[i].val ){
                        dp[i].val = dp[j].val + 1;
                        dp[i].list = new ArrayList<>(dp[j].list);
                        dp[i].list.add(nums[i]);
                       if (dp[i].val > max){
                           max = dp[i].val;
                           index = i;
                       }
                    }
                }
            }
        }
        return dp[index].list;
    }
}
